package ArithMathOperation;
//*************************************************************************************
//    SuffixExpression.java        Author:王禹涵
//
//    中缀转为后缀的类，对NifixExpression产生的中缀式子进行转换。
//*************************************************************************************
import java.util.*;

public class SuffixExpression
{
    public String SuffixExpression(String num)
    {
        Stack<String> OPND = new Stack<>();//设操作数栈OPND
        Stack<String> OPTR = new Stack<>();//设运算符栈OPTR
        Stack<String> number = new Stack<>();//设另一个操作数栈存放数字字符
        OPTR.push("#");//将"#"压入栈底
        String a ;
        String b ;//b为当前读入的运算符
        String c ;
        String y ;
        String z ;
        String suffix = "";
        String suf = "";
        String str = "";
        String str2 = "";

        String[] result = num.split("\\s");
        for (int x = 0; x < result.length; x++)
        {
            if ("+".equals(result[x]) || "-".equals(result[x]) || "*".equals(result[x]) || "÷".equals(result[x]) || "(".equals(result[x]) || ")".equals(result[x]) || "#".equals(result[x]) || "=".equals(result[x]))
            {
                if ("+".equals(result[x]) || "-".equals(result[x]) || "*".equals(result[x]) || "÷".equals(result[x]) || "(".equals(result[x]) || ")".equals(result[x]) || "#".equals(result[x]))
                {
                    b = result[x];
                    a = OPTR.peek();
                    if ("+".equals(a) || "-".equals(a))
                    {
                        if ("+".equals(b) || "-".equals(b) || ")".equals(b) || "#".equals(b))
                        {
                            if (")".equals(b))
                            {
                                while (")".equals(result[x]) && !"(".equals(OPTR.peek()))
                                {
                                    c = OPTR.pop();
                                    z = OPND.pop();
                                    y = OPND.pop();
                                    str += y;
                                    str += " ";
                                    str += z;
                                    str += " ";
                                    str += c;
                                    str += " ";
                                    OPND.push(str);
                                    str = "";
                                }
                                if (")".equals(result[x]) && "(".equals(OPTR.peek()))
                                {
                                    OPTR.pop();
                                }
                            }
                            else
                                {
                                    c = OPTR.pop();
                                    z = OPND.pop();
                                    y = OPND.pop();
                                    str += y;
                                    str += " ";
                                    str += z;
                                    str += " ";
                                    str += c;
                                    str += " ";
                                    OPND.push(str);
                                    str = "";
                                    OPTR.push(result[x]);
                                }
                        }

                        else if ("*".equals(b) || "÷".equals(b) || "(".equals(b))
                        {
                            OPTR.push(result[x]);
                        }//当a的优先级小于b时，b压入OPTR栈.
                    }

                    if ("*".equals(a) || "÷".equals(a))
                    {
                        if ("(".equals(b))
                        {
                            OPTR.push(result[x]);
                        } else
                            {
                                if (")".equals(b))
                                {
                                    while (")".equals(result[x]) && !"(".equals(OPTR.peek()))
                                    {
                                        c = OPTR.pop();
                                        z = OPND.pop();
                                        y = OPND.pop();
                                        suffix += y;
                                        suffix += " ";
                                        suffix += z;
                                        suffix += " ";
                                        suffix += c;
                                        suffix += " ";
                                        OPND.push(suffix);
                                        suffix = "";
                                    }
                                if (")".equals(result[x]) && "(".equals(OPTR.peek()))
                                {
                                    OPTR.pop();
                                }
                            }
                            else
                                {
                                    c = OPTR.pop();
                                    z = OPND.pop();
                                    y = OPND.pop();
                                    suffix += y;
                                    suffix += " ";
                                    suffix += z;
                                    suffix += " ";
                                    suffix += c;
                                    suffix += " ";
                                    OPND.push(suffix);
                                    suffix = "";
                                    OPTR.push(result[x]);
                                }

                            }
                    }

                    if ("(".equals(a))
                    {
                        if (")".equals(b))
                        {
                            OPTR.pop();
                        }//当a = b 时，a从OPTR出栈.
                        if ("+".equals(b) || "-".equals(b) || "*".equals(b) || "÷".equals(b) || "(".equals(b))
                        {
                            OPTR.push(result[x]);
                        }
                    }

                    if (")".equals(a))
                    {
                        if (")".equals(b))
                        {
                            while (")".equals(result[x]) && !"(".equals(OPTR.peek()))
                            {
                                c = OPTR.pop();
                                z = OPND.pop();
                                y = OPND.pop();
                                str2 += y;
                                str2 += " ";
                                str2 += z;
                                str2 += " ";
                                str2 += c;
                                str2 += " ";
                                OPND.push(str2);
                                str2 = "";
                            }
                            if (")".equals(result[x]) && "(".equals(OPTR.peek()))
                            {
                                OPTR.pop();
                            }
                        }
                        else
                            {
                                c = OPTR.pop();
                                z = OPND.pop();
                                y = OPND.pop();
                                str2 += y;
                                str2 += " ";
                                str2 += z;
                                str2 += " ";
                                str2 += c;
                                str2 += " ";
                                OPND.push(str2);
                                str2 = "";
                                OPTR.push(result[x]);
                            }
                    }

                    if ("#".equals(a))
                    {
                        if ("+".equals(b) || "-".equals(b) || "*".equals(b) || "÷".equals(b) || "(".equals(b))
                        {
                            OPTR.push(result[x]);
                        }

                        if ("#".equals(b))
                        {
                            OPTR.pop();
                        }
                    }
                }

                if ("=".equals(result[x]))
                {
                    while (OPND.size() != 0)
                    {
                        number.push(OPND.pop());
                    }

                    suf += " ";
                    suf += number.pop();
                    while (number.size() != 0)
                    {
                        suf += " ";
                        suf += number.pop();
                    }
                    while (OPTR.peek() != "#")
                    {
                        suf += " ";
                        suf += OPTR.pop();
                    }
                    suf += " ";
                    suf += "=";
                }
        }
        else
            {
                OPND.push(result[x]);
            }
        }
        return suf;
    }
}